#include <stdio.h>

void swap(int* a,int* b)
{
	int p = *a;
	*a = *b;
	*b = p;
}
void Adjustdown(int* a,int parent, int n)
{
	int child = parent*2+1;
	while (child<n)
	{
		if (child+1<n&&a[child] > a[child + 1])
			child = child + 1;
		if (a[child] < a[parent])
			swap(&a[child],&a[parent]);
		parent= child;
		child = parent * 2 + 1;
	}
	
}
void heap_sort(int* a,int n)
{
	for (int i = (n - 2) / n;i >= 0;i--)
	{
		Adjustdown(a, i, n);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		Adjustdown(a, 0, end);
		end--;
	}
}
int main()
{
	int a[] = { 1,9,8,5,6,4,7,4 };
	heap_sort(a,7);
	for (int i = 0;i < 8;i++)
	{
		printf("%d ", a[i]);
	}
		return 0;
}